#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    bool is_valid(vector<vector<char>> &board, int row, int col, int val)
    {
        // same row
        for (size_t i = 0; i < 9; i++)
        {
            if (board[row][i] == val + '0')
            {
                return false;
            }
        }

        // same col
        for (size_t i = 0; i < 9; i++)
        {
            if (board[i][col] == val + '0')
            {
                return false;
            }
        }

        // 3*3 blank
        size_t start_row = (row / 3) * 3;
        size_t start_col = (col / 3) * 3;
        for (size_t i = start_row; i < start_row + 3; i++)
        {
            for (size_t j = start_col; j < start_col + 3; j++)
            {
                if (board[i][j] == val + '0')
                {
                    return false;
                }
            }
        }

        return true;
    }
    bool tracebacking(vector<vector<char>> &board)
    {
        for (size_t i = 0; i < 9; i++)
        {
            for (size_t j = 0; j < 9; j++)
            {
                if (board[i][j] != '.')
                {
                    continue;
                }
                for (size_t num = 1; num <= 9; num++)
                {
                    if (is_valid(board, i, j, num))
                    {
                        board[i][j] = num + '0';
                        if (tracebacking(board))
                        {
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>> &board)
    {
        tracebacking(board);
    }
};

int main()
{
    vector<vector<char>> board{
        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
    for (auto vec : board)
    {
        for (auto ch : vec)
        {
            cout << ch;
        }
        cout << endl;
    }
    cout << endl;
    Solution sol;
    sol.solveSudoku(board);
    for (auto vec : board)
    {
        for (auto ch : vec)
        {
            cout << ch;
        }
        cout << endl;
    }
}